//给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。
// 返回的结果必须要是按升序排好的。
//
// 整数 a 比整数 b 更接近 x 需要满足： 
//
// 
// |a - x| < |b - x| 或者 
// |a - x| == |b - x| 且 a < b 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：arr = [1,2,3,4,5], k = 4, x = 3
//输出：[1,2,3,4]
// 
//
// 示例 2： 
//
// 
//输入：arr = [1,2,3,4,5], k = 4, x = -1
//输出：[1,2,3,4]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= k <= arr.length 
// 1 <= arr.length <= 10⁴ 
// 数组里的每个元素与 x 的绝对值不超过 10⁴ 
// 
// Related Topics 数组 双指针 二分查找 排序 堆（优先队列） 👍 259 👎 0


import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> ret = Arrays.stream(arr).boxed().collect(Collectors.toList());
        int n = ret.size();
        //如果x <=首元素，则返回前k个元素
        if(x <= ret.get(0)){
            return ret.subList(0, k);
            // //如果x >= 尾元素，则返回后k个元素
        }else if(x >= ret.get(n-1)){
            return ret.subList(n - k, n);
            //x介于arr[0]和arr【n-】
        }else {
            //如果x在数组中，返回下标，否则返回-(插入键)-1,插入键为大于key的第一个元素
            int index = Collections.binarySearch(ret, x);
            //此时index= -(大于x的第一个数) - 1
            if(index < 0){
                //返回大于x的第一个数
                index = -index - 1;
            }
            //index - k - 1
            int low = Math.max(0, index - k );

            int high = Math.min(n - 1, index + k - 1);

            while (high - low > k - 1){
                if(ret.get(high) - x < x - ret.get(low)  ){
                    low ++;
                }else {
                    high--;
                }
            }
            return ret.subList(low, high + 1);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
